Various product inspection apparatus and methods are utilized in industrial, manufacturing and research settings for the inspection of end products for flaws and defects to insure product quality. Visual inspection is one type of product inspection utilized in industrial and manufacturing quality control. Certain visual inspection methods and apparatus test for cosmetic integrity utilizing visual inspection machines or the human eye. Cosmetic integrity inspection differs from another type of inspection, inspection for functional integrity, which can be tested using electronic probes.
Human inspection for cosmetic integrity deteriorates in quality as the human eye is distracted by the repetition and exacting nature of visual inspection. The costs and inaccuracies associated with human inspection and the increase in automated manufacturing systems have contributed to the increase in interest in automated visual inspection machines and methods.
Automated visual inspection machines generally have been designed having a viewing device, for example an optical input device, utilized to acquire images of the product being inspected. These optical input devices typically include devices such as charge coupled device (CCD) cameras or laser sensors. The images acquired by these optical input devices may be processed using artificial intelligence algorithms seeking perturbations that indicate product defects or manufacturing flaws. Automated inspection has occurred with various methods including reference comparison and analysis of generic properties. Automated visual inspection has been utilized in inspecting electronics products and components including printed circuit boards (PCB). Such PCBs generally include a dielectric substrate having conductive traces printed therein. Integrated circuit components are mounted to the board providing an electrical connection with the conductive traces of the board. Inspection of various regions of the PCBs has been conducted including final post assembly inspection.
Automated visual inspection devices typically have had a limited or constrained viewing area for acquiring these images. Generally, the products or objects being inspected are larger than a single viewing area of the optical input device. The viewing area is therefore typically required to be moved relative to the product during inspection. Servo motors have been employed to move the product or the input device relative to one another in order to acquire images of product.
Some problems associated with controlling the movement of inspection machines have been described as route or path planning problems. Attempts to solve these problems have been concerned with planning an inspection route which avoids obstacles or collisions with objects being inspected. Such inspection path planning problems have been attempted as seeking solutions to combinatorial problems. Combinatorial problems are problems in which the decision variables are discrete, i.e. where the solution is a set or a sequence or integers or other discrete objects. A discussion of combinatorial problems can be found in Reeves, C., Modern Heuristic Techniques for Combinatorial Problems, Chp. 1, Reeves, C. and Beasley, J., Introduction, pp. 1-19 (Halstead Press 1993) the disclosure of which is hereby incorporated by reference.
The problem of finding optimal solutions to such combinatorial problems is known as combinatorial optimization. Examples of such combinatorial problems are the quadratic assignment problem, the zero-to-one knapsack problem, the set covering problem, the vehicle routing problem, and the like. Solving combinatorial problems generally involves searching among local optimum for the true or global optimum. Local optima can be found in relation to neighborhoods where moves or operations find a better solution in a neighborhood, thus providing a local optima with respect to the neighborhood. In some instances, a local optima is also a global optima. Techniques called heuristics have been utilized in seeking to solve or optimize such combinatorial problems. Such heuristics seek near optimal solutions at a reasonable computational cost. Heuristics often cannot guarantee an optimal solution or foretell the degree or proximity to optimality of a particular solution. Some combinatorial problems are inherently of exponential complexity, and referred to generally as "nondeterministic polynomial" or NP-hard problems.
In visual inspection of certain electronic components or products, path planning or routing optimization has been attempted by applying algorithms to optimization problems. For example, a traveling salesman in a plane problem was utilized for minimizing the time spent visiting each point from a predetermined list of inspection points generated from a CAD layout data. Mahon, Harris and Vernon, "Automated Visual Inspection of Solder Paste Deposition on Surface Mount Technology PCB's," Computers in Industry 12, pp. 31-42 (1989) ("Mahon, et al"). Mahon, et al. applied the Simulated Annealing algorithm for a suboptimal solution. Mahon, et al. however, described a process of inspection utilizing the recognition properties of inspection.
With respect to attempts of optimization of a control path for automated visual inspection, one prior strategy has been to divide an entire region or product surface into a uniformly spaced grid of viewing areas. For example, the product to be inspected can be divided into columns and views can be created preceding in a vertical direction along each column. All regions of interest are included in at least one viewing area. For example, each grid element is then inspected progressing through a row-by-row analysis regardless of the placement of objects of interest. This method may require traveling over an entire surface when only portions of the surface or inspection area contain objects of interest for inspection. Objects of interest in products tend to cluster together. This method was typically repeated for each level of magnification of inspection. Thus, this method results in wasted inspection time and increased operating wear on inspection equipment and increased labor, computational, operational and repair costs. Further, increases in inspection time multiply in automated manufacturing environments to reduce the rate of production and thereby lower output and productivity.
There is, therefore, a need to provide solutions to the problem of automated visual inspection of regions of interest utilizing a constrained view which reduces the time of inspection and which improves the route of inspection travel over products having discrete and dispersed regions of interest.